package demo;

import java.util.Arrays;

//插入排序
public class InsertSort {

    //对数组全部做插入排序
    public static void insertSort(int[]arr,int size){
        //一开始认为第一个数已经有序
        for(int i=1;i<size;i++){
            //有序区间 [0,i)
            //无序区间 [i,size)
            //再倒着遍历有序区间，找到合适插入位置
            int key=arr[i];
            int j=i-1;
            for( j=i-1;j>=0&&key<arr[j];j--){
                //要提前把不合适的位置往后搬
                arr[j+1]=arr[j];
            }
            //循环结束，表明key>=arr[j]找到了合适的插入位置
            //找到key>=arr[j]后，插入到arr[j]的后面就是arr[j+1]位置
            arr[j+1]=key;
        }
    }
    //对指定范围做插入排序
    public static void insertSort2(int[]arr,int formIndex,int toIndex){
        int n=toIndex-formIndex;
        for(int i=1;i<n;i++){
            //有序区间 [formIndex,formIndex+i)
            //无序区间 [formIndex+i,size)
            //插入的有序区间的元素下标[formIndex+i]

            int key=arr[i];
            //要先保存无序区间需要拿出的去插入的元素
            int j=formIndex+i-1;
            //倒着遍历有序区间，能够提前把不合适的位置往后移动，找到合适的插入位置
            for(j=formIndex+i-1;j>=formIndex&&key<arr[j];j--){
                arr[j+1]=arr[j];
            }
            //循环结束 表明找到了合适的插入位置
            arr[j+1]=key;
        }
    }

    public static void main(String[] args) {
        int[]arr={2,7,5,9,1,5,8};
        insertSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
        int []arr2=arr;
        insertSort2(arr,0,7);
        System.out.println(Arrays.toString(arr2));

    }
}
